/**
 * \file Hashtable.h
 * \brief Hashtable implementations
 * \author Corey Tabaka
 */

/*
   Copyright 2006 Corey Tabaka

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
*/

#include <ktypes.h>
#include <Log.h>
#include <hash.h>

#ifndef __KERNEL_HASHTABLE_H__
#define __KERNEL_HASHTABLE_H__

template <class key_type>
uint GenericHashFunc(key_type &key) {
	return joaat_hash(&key, sizeof(key_type));
}

template <class key_type, class value_type,
	uint (*hash_func)(key_type &key)=GenericHashFunc<key_type> >
class Hashtable {
	protected:

	uint count;
	uint capacity;
	uint maxLoad;
	uint indexMask;

	typedef struct _record {
		key_type key;
		value_type value;

		_record *next;
		_record *prev;
	} record_t;

	typedef struct {
		uint count;
		record_t *head;
		record_t *tail;
	} bucket_t;

	bucket_t *buckets;

	public:

	Hashtable(uint initCapacity=1024, uint initMaxLoad=85) {
		capacity = initCapacity >= 2 ? NLP2(initCapacity) : 2;
		maxLoad = initMaxLoad < 100 ? initMaxLoad : 100;
	
		count = 0;
		indexMask = capacity - 1;
		buckets = new bucket_t[capacity];
	
		memset(buckets, 0, sizeof(bucket_t) * capacity);
	}
	
	~Hashtable(void) {
		for (uint i=0; i < capacity; i++) {
			record_t *record = buckets[i].head;
			while (record) {
				record_t *temp = record->next;
				dequeue(buckets + i, record);
				
				delete record;
				
				record = temp;
			}
		}
		
		delete [] buckets;
	}

	void put(key_type key, value_type value) {
		uint hashIndex = hash_func(key) & indexMask;
	
		bucket_t *bucket = buckets + hashIndex;
		record_t *record = bucket->head;
		for (; record && record->key != key; record = record->next);
	
		if (!record) {
			record = new record_t;
			record->key = key;
	
			enqueue(bucket, record);
	
			bucket->count++;
			count++;
		}
	
		record->value = value;
		
		checkLoad();
	}
	
	bool get(key_type key, value_type &value) {
		uint hashIndex = hash_func(key) & indexMask;
	
		bucket_t *bucket = buckets + hashIndex;
		record_t *record = bucket->head;
		for (; record && record->key != key; record = record->next);
	
		if (record) {
			value = record->value;
		}
	
		return record != 0;
	}
	
	bool containsKey(key_type key) {
		uint hashIndex = hash_func(key) & indexMask;
	
		bucket_t *bucket = buckets + hashIndex;
		record_t *record = bucket->head;
		for (; record && record->key != key; record = record->next);
	
		return record != 0;
	}
	
	bool remove(key_type key) {
		uint hashIndex = hash_func(key) & indexMask;
	
		bucket_t *bucket = buckets + hashIndex;
		record_t *record = bucket->head;
		for (; record && record->key != key; record = record->next);
	
		if (record) {
			bucket->count--;
			count--;
	
			dequeue(bucket, record);
	
			delete record;
		}
	
		return record != 0;
	}
	
	void status(void) {
		Log::printf(LOG_LOW, "Hashtable:\n");
		Log::printf(LOG_LOW, "    %u element capacity\n", capacity);
		Log::printf(LOG_LOW, "    %u current elements\n", count);
		Log::printf(LOG_LOW, "    %f%% load (%u)\n", count * 100.0f / capacity,
			count * 100 / capacity);
		Log::printf(LOG_LOW, "    %08x index mask\n", indexMask);
		
		uint clustered = 0;
		uint maxBucketLoad = 0;
		for (uint i=0; i < capacity; i++) {
			if (buckets[i].count > maxBucketLoad) {
				maxBucketLoad = buckets[i].count;
			}
			
			if (buckets[i].count > 1) {
				clustered += buckets[i].count;
			}
		}
		
		Log::printf(LOG_LOW, "    %f%% clustered\n", clustered * 100.0f / count);
		Log::printf(LOG_LOW, "    %d max bucket load\n", maxBucketLoad);
	}

	void dump(void) {
		status();
		
		Log::printf(LOG_LOW, "\nContents:\n");
		
		for (uint i=0; i < capacity; i++) {
			if (buckets[i].count > 0) {
				if (i > 0 && buckets[i-1].count == 0) {
					Log::printf(LOG_LOW, "...\n");
				}
				
				Log::printf(LOG_LOW, "%8u. %u elements\n", i, buckets[i].count);
			}
		}
		
		if (buckets[capacity-1].count == 0) {
			Log::printf(LOG_LOW, "...\n");
		}
	}
	
	protected:
	/**
	 * Find the least power of two that is equal or greater than argument.
	 * Valid arguments are in the range of 0 to 0x7fffffff.
	 */
	static uint NLP2(uint val) {
		val &= 0x7fffffff;
	
		uint i;
		for (i=0x40000000; i > 1; i >>= 1) {
			if ((i & val) == i) {
				break;
			}
		}
	
		return val > i ? i << 1 : i;
	}
	
	void checkLoad(void) {
		uint load = count * 100 / capacity;
		
		if (load > maxLoad && capacity < 0x80000000) {
			status();
			
			bucket_t *tbuckets = buckets;
			uint tcapacity = capacity;
			
			// update the capacity to the next power of two
			capacity <<= 1;
			indexMask = capacity - 1;
			
			buckets = new bucket_t[capacity];
			
			// copy entries in the first half and clear the second half
			memcpy(buckets, tbuckets, sizeof(bucket_t) * tcapacity);
			memset(buckets + tcapacity, 0, sizeof(bucket_t) * tcapacity);
			
			delete [] tbuckets;
			tbuckets = 0;
			
			// rehash records that aren't positioned correctly
			for (uint i=0; i < tcapacity; i++) {
				record_t *record = buckets[i].head;
				while (record) {
					record_t *temp = record->next;
					
					uint hashIndex = hash_func(record->key) & indexMask;
					
					// move the record to the correct bucket
					if (hashIndex != i) {
						buckets[i].count--;
						
						dequeue(buckets + i, record);
						enqueue(buckets + hashIndex, record);
						
						buckets[hashIndex].count++;
					}
					
					record = temp;
				}
			}
			
			status();
		}
	}
	
	static void enqueue(bucket_t *bucket, record_t *record) {
		record->next = NULL;
		
		if (bucket->head) {
			record->prev = bucket->tail;
			bucket->tail->next = record;
		} else {
			record->prev = NULL;
			bucket->head = record;
		}
	
		bucket->tail = record;
	}
	
	static void dequeue(bucket_t *bucket, record_t *record) {
		bool isHead = record == bucket->head;
		bool isTail = record == bucket->tail;
	
		if (isTail) {
			bucket->tail = record->prev;
	
			if (!isHead) {
				record->prev->next = NULL;
			}
		}
	
		if (isHead) {
			bucket->head = record->next;
	
			if (!isTail) {
				record->next->prev = NULL;
			}
		}
	
		if (!isHead && !isTail) {
			record->prev->next = record->next;
			record->next->prev = record->prev;
		}
	}
};

#endif
